package leetcode.code0057;

import java.util.Arrays;

public class Solution extends Solution57 {

	@Override
	public int[][] insert(int[][] intervals, int[] newInterval) {
		int len = intervals.length;
		if (len == 0) {
			return new int[][] { newInterval };
		}
		int[][] array = new int[len + 1][2];
		for (int i = 0; i < len; i++) {
			array[i] = intervals[i];
		}
		array[len] = newInterval;
		Arrays.sort(array, (a, b) -> a[0] - b[0]);
		int p = 0; // 向intervals上p位置合并区间
		for (int i = 1; i < array.length; i++) {
			if (f(array[p], array[i])) {// 能合并, 合并的结果给p持有 , 继续向p合并i
				array[p][1] = Math.max(array[p][1], array[i][1]); // 区间能合并, 接入intervals[i]的区间尾部
			} else {
				array[++p] = array[i];// 不能合并, p向下移动一位 , 将i位置给p
			}
		}
		int[][] ans = new int[p + 1][2];
		for (int i = 0; i <= p; i++) {
			ans[i] = array[i];
		}
		return ans;
	}

	private boolean f(int[] arr1, int[] arr2) {
		int left = Math.max(arr1[0], arr2[0]);
		int right = Math.min(arr1[1], arr2[1]);
		if (left <= right) {
			return true;
		}
		return false;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		so.debug5();
		so.debug6();

	}

}
